package leetcode;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @Description 1738. 找出第 K 大的异或坐标值
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.5.19
 */

public class T1738 {
    public static void main(String[] args) {
        T1738 t1738 = new T1738();
        int[][] matrix ={ {8,10,5,8,5,7,6,0,1,4,10,6,4,3,6,8,7,9,4,2}};
        int k = 1;
        System.out.println(t1738.kthLargestValue(matrix, k));
    }

    public int kthLargestValue(int[][] matrix, int k) {
        int[][] rows = new int[matrix.length + 1][matrix[0].length + 1];
        int[][] cols = new int[matrix.length + 1][matrix[0].length + 1];
        int[][] result = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                rows[i + 1][j + 1] = rows[i + 1][j] ^ matrix[i][j];
            }
        }


        for (int x = 0; x < matrix[0].length; x++) {
            for (int y = 0; y < matrix.length; y++) {
                cols[y + 1][x + 1] = cols[y][x + 1] ^ matrix[y][x];
            }
        }

        List<Integer> datas = new ArrayList();
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                result[i + 1][j + 1] = result[i][j] ^ rows[i + 1][j] ^ cols[i + 1][j + 1];
//                System.out.println(i+" "+ j+" "+ (result[i + 1][j + 1]));
                datas.add(result[i+1][j+1] );
            }
        }

        List<Integer> collect = datas.stream().sorted(Comparator.comparing(Integer::intValue).reversed()).collect(Collectors.toList());

        return collect.get(k-1);
    }
}
